package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC309 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            if (n <= 1) return 0;

            int[][] dp = new int[n][3];
            dp[0][0] = 0;
            dp[0][1] = -1 * prices[0];
            dp[0][2] = 0;

            for (int i = 1; i < n; i++) {//从[1]...[n-1]
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
                dp[i][2] = dp[i - 1][1] + prices[i];
            }

            return Math.max(dp[n - 1][0], dp[n - 1][2]);
        }
    }


    class Solution_Exceed_Time_Limit {
        Map<String, Integer> memo = new HashMap<>();

        public int maxProfit(int[] prices) {
            return dfs(prices, 0, -1, -2, 0);
        }

        /**
         * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
         *
         * @param prices
         * @param curDayIdx
         * @param lastAction -1:上一步沿袭的动作是卖出，1:上一步沿袭的动作是买入
         *                   当前动作有三种：1.保持lastAction，2.买入，3.卖出
         * @return
         */
        public int dfs(int[] prices, int curDayIdx, int lastAction, int lastSoldDate, int lastBenefit) {
            if (curDayIdx >= prices.length) return lastBenefit;
            String curStatusKey = "" + curDayIdx + "_" + String.valueOf(lastAction) + "_" + String.valueOf(lastSoldDate) + "_" + lastBenefit;
            if (memo.containsKey(curStatusKey)) return memo.get(curStatusKey);

            // 之前是卖掉了，现在可以买入，但是需要考虑冷冻期
            if (-1 == lastAction) {
                if (curDayIdx - lastSoldDate > 1) {
                    // 已经过了冷冻期，可以重新买，也可以保持原状
                    int curBuyBenefit = dfs(prices, curDayIdx + 1, 1, lastSoldDate, lastBenefit) - prices[curDayIdx];
                    int curKeep = dfs(prices, curDayIdx + 1, -1, lastSoldDate, lastBenefit);
                    memo.put(curStatusKey, Math.max(curBuyBenefit, curKeep));
                    return Math.max(curBuyBenefit, curKeep);
                } else {
                    //尚且在冷冻期，只能保持原状
                    int curKeep = dfs(prices, curDayIdx + 1, -1, lastSoldDate, lastBenefit);
                    memo.put(curStatusKey, curKeep);
                    return curKeep;
                }
            } else {
                // 之前是买入，现在可以卖，也可以保持原买入
                int curSellBenefit = dfs(prices, curDayIdx + 1, -1, curDayIdx, lastBenefit) + prices[curDayIdx];
                int curKeep = dfs(prices, curDayIdx + 1, 1, lastSoldDate, lastBenefit);
                memo.put(curStatusKey, Math.max(curSellBenefit, curKeep));
                return Math.max(curSellBenefit, curKeep);
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3,0,2]");
        System.out.println(solution.maxProfit(arr));
    }

    public static void main(String[] args) throws Exception {
        LC309 an = new LC309();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
